package binaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Queue;

/**
 * 实现哈夫曼算法
 * 
 * */

public class HuffmanTree<AnyType> {
	
	/**创建哈弗曼树
	 * */
	public static <AnyType> Node<AnyType> createTree(List<Node<AnyType>> nodes){
		while(nodes.size() > 1){
			//逆序排序
			Collections.sort(nodes);
			Node<AnyType> left = nodes.get(nodes.size()-1);
			Node<AnyType> right = nodes.get(nodes.size()-2);
			Node<AnyType> parent = new Node<AnyType>(null, left.getWeight()+right.getWeight());
			parent.setLeft(left);
			parent.setRight(right);
			nodes.remove(left);
			nodes.remove(right);
			nodes.add(parent);
		}
		//得到根节点
		return nodes.get(0);
	}
	//层次遍历哈弗曼树
	public static <AnyType> List<Node<AnyType>> breadth(Node<AnyType> root){
		List<Node<AnyType>> list = new ArrayList<Node<AnyType>>();
		Queue<Node<AnyType>> queue = new ArrayDeque<Node<AnyType>>();
		
		if(root != null){
			queue.add(root);
		}
		
		while(!queue.isEmpty()){
			//得到队列的首节点，并不删除该节点
			list.add(queue.peek());
			Node<AnyType> node = queue.poll();
			
			if(node.getLeft() != null){
				queue.add(node.getLeft());
			}
			
			if(node.getRight() != null){
				queue.add(node.getRight());
			}
		}
		return list;
	}
	
	//测试函数
	public static void main(String[] args) {
		
		List<Node<String>> list = new ArrayList<Node<String>>();
		//向链表中添加元素及其权值
		list.add(new Node<String>("a",7));
		list.add(new Node<String>("b",5));
		list.add(new Node<String>("c",4));
		list.add(new Node<String>("d",2));
		
		Node<String> root = HuffmanTree.createTree(list);
//		System.out.println(HuffmanTree.breadth(root));
		List<Node<String>> list1 = HuffmanTree.breadth(root);
		Iterator itr=list1.iterator();
		while(itr.hasNext()){
			Node<String> node=(Node<String>) itr.next();
			System.out.println(node.getData()+"\t"+node.getWeight());
		}
	}
	
}

//继承Comparable接口，实现排序
class Node<AnyType> implements Comparable<Node<AnyType>> {
	private AnyType data;
	private double weight;
	private Node<AnyType> left;
	private Node<AnyType> right;
	
	public Node(AnyType data, double weight){
		this.data = data;
		this.weight = weight;
	}
	
	public AnyType getData() {
		return data;
	}

	public void setData(AnyType data) {
		this.data = data;
	}

	public double getWeight() {
		return weight;
	}

	public void setWeight(double weight) {
		this.weight = weight;
	}

	public Node<AnyType> getLeft() {
		return left;
	}

	public void setLeft(Node<AnyType> left) {
		this.left = left;
	}

	public Node<AnyType> getRight() {
		return right;
	}

	public void setRight(Node<AnyType> right) {
		this.right = right;
	}

	@Override
	public String toString(){
		return "data:"+this.data+";weight:"+this.weight;
	}

	@Override
	//实现Collections.sort(n)的重写，实现链表的逆序排序
	public int compareTo(Node<AnyType> other) {
		if(other.getWeight() > this.getWeight()){
			return 1;
		}
		if(other.getWeight() < this.getWeight()){
			return -1;
		}
		
		return 0;
	}
}


